package com.epam.mycollections.lists;

import com.epam.mycollections.interfaces.*;

import java.util.Iterator;

/**
 * My Personal Single Linked List
 *
 * @author Iurii Miedviediev
 * @version 1.0 Build 02.03.2014
 *
 */
public class MyLinkedList<E extends Comparable<E>> implements MyList<E>, MyQueue<E>, MyStack<E> {

    /**
     * Element of the Linked List
     */
    private static class Node<E> {
        // Structure for the Element
        private E value;
        private Node<E> next;

        //constructor for Element
        public Node(E newValue) {
            value = newValue;
        }

        // value getter/setter
        public E getValue() {
            return value;
        }

        public void setValue(E newValue) {
            value = newValue;
        }

        // next element getter/setter
        public Node<E> getNext() {
            return next;
        }
        public void setNext(Node<E> newNext) {
            next = newNext;
        }

        // check for the next element
        public boolean hasNext() {
            return !(next==null);
        }
    }

    public static final int HASHSALT = 31;

    //Head of the list, fake Element
    private final Node<E> head = new Node(null);

    //helpers, pointers to current element and the element next to it
    Node<E> current;
    Node<E> next;

    //default constructor
    public MyLinkedList() {
    }

    //constructor with argument
    public MyLinkedList(MyList<E> c) {
        for(E element : c) {
            this.add(element);
        }
    }

    /**
     * Compute the size of the Linked List (the number of its valuable elements)
     *
     * @return integer, size of the Linked List
     */
    @Override
    public int size() {
        int length = 0;
        current = head.getNext();
        //counts elements one by one up to the end
        while(!(current==null)) {
            length++;
            current = current.getNext();
        }
        return length;
    }

    /**
     * This method adds new Element to the end of the Linked List
     *
     * @param e	value of the Element
     */
    @Override
    public void add(E e) {
        // if Linked List is empty, place new Element at start of it
        if(head.getNext()==null) {
            head.setNext(new Node<E>(e));
        } else {
            //pointers to current element and the next element to it
            current = head.getNext();
            next = current.getNext();

            //move up to the end of the Linked List
            while(!(next==null)) {
                current = current.getNext();
                next = current.getNext();
            }
            //current is now pointing to the last element of the Linked List
            current.setNext(new Node<E>(e));
        }
    }

    /**
     * Add a new Element to a certain place in the Linked List <br>
     * In case of negative index or index bigger than size of the Linked List,
     * element would just be added to the end of the List
     *
     * @param index		desirable position of the element
     * @param element	new Element to add to the Linked List
     */
    @Override
    public void add(int index, E element) {
        //check the correctness of index
        if(index < 0 || index > this.size()) {
            throw new MyIndexOutOfBoundsException();
        }

        //in List is empty, or index is the last one in the List, just add to the end
        if(this.isEmpty() || index == this.size()) {
            this.add(element);
        } else {
            int counter = 0;
            current = head;
            next = current.getNext();

            //find necessary position in the List
            while (counter!=index) {
                current = current.getNext();
                next = current.getNext();
                counter++;
            }
            //insert element to appropriate position and point to the rest of the List
            current.setNext(new Node<E>(element));
            current = current.getNext();
            current.setNext(next);
        }
    }

    /**
     * Add element to the start of the Linked List
     *
     * @param e		new Element to be added
     */
    public void addFirst(E e) {
        this.add(0, e);
    }

    /**
     * Add element to the end of the Linked List
     * Duplicate of the standard add(Integer e) method
     *
     * @param e		new Element to be added
     */
    public void addLast(E e) {
        this.add(e);
    }

    /**
     * Get value of the Element at certain position
     * In case of negative index or index bigger than size of the Linked List,
     * method would return null
     *
     * @param index		natural, position in the Linked List
     * @return	value of the Element
     */
    @Override
    public E get(int index) {
        //check the correctness of index
        if(index < 0 || index > this.size()) {
            throw new MyIndexOutOfBoundsException();
        }

        int counter = 0;
        current = head.getNext();
        //path through the List and find necessary position
        while (counter!=index) {
            current = current.getNext();
            counter++;
        }
        //take the value of the Element and return
        if(current == null) {
            return null;
        }
        return current.getValue();
    }

    /**
     * Get value of the first Element
     * @return	value of the first Element
     */
    public E getFirst() {
        return this.get(0);
    }

    /**
     * Get value of the last Element
     * @return value of the last Element
     */
    public E getLast() {
        return this.get(this.size()-1);
    }

    /**
     * Remove an Element at a certain index and return it
     * In case of empty Linked List or incorrect index, returns null
     *
     * @param index		position in the Linked List
     * @return	removed element
     */
    @Override
    public E remove(int index) {
        //check the correctness of index
        if(index < 0 || index > this.size()) {
            throw new MyIndexOutOfBoundsException();
        }

        //if List is empty, nothing to remove
        if (this.isEmpty()) {
            return null;
        } else {
            int counter = 0;
            current = head;
            next = current.getNext();

            //find appropriate element
            while (counter!=index) {
                current = current.getNext();
                next = current.getNext();
                counter++;
            }
            //remember removed element to return it
            Node<E> removed = next;
            //tie current element to the element next to removed
            next = next.getNext();
            current.setNext(next);
            return removed.getValue();
        }
    }

    /**
     * Removes and returns the first element of the Linked List
     *
     * @return	removed element
     */
    public E removeFirst() {
        return this.remove(0);
    }

    /**
     * Removes and returns the last element of the Linked List
     *
     * @return	removed element
     */
    public E removeLast() {
        return this.remove(this.size()-1);
    }

    /**
     * Set the value of Element at certain position
     * Ignores the operation in case of incorrect index
     *
     * @param index position of the Element
     * @param element	new value of the Element
     */
    @Override
    public void set(int index, E element) {
        //check the correctness of index
        if(index < 0 || index > this.size()) {
            throw new MyIndexOutOfBoundsException();
        }

        int counter = 0;
        current = head.getNext();

        //find necessary element
        while (counter!=index) {
            current = current.getNext();
            counter++;
        }
        //update its value
        current.setValue(element);
    }

    /**
     * Get the index of an Element with certain value
     * In case of not finding element with necessary value, returns -1
     *
     * @param o		Integer, value to find
     * @return		index of Element with matching value
     */
    @Override
    public int indexOf(E o) {
        int index = 0;
        current = head.getNext();
        while(current != null) {
            //find first element with necessary value
            if(o.equals(current.getValue())) {
                return index;
            }
            current = current.getNext();
            index++;
        }
        //in case of incorrect or not found value, return -1
        return -1;
    }

    /**
     * Check the equality of current MyLinkedList with the other one
     * @param other	Other MyLinkedList to check whether it is equal to the current one
     * @return	true, if lists are equal, false otherwise
     */
    @Override
    public boolean equals(Object other) {
        if(!(other instanceof MyList)) {
            return false;
        }
        MyList<E> list = (MyList<E>) other;
        //if lists have different sizes, they are not equal
        if(this.size() != list.size()) {
            return false;
        } else {

            //check the equality of every element in the lists
            for(int pos=0, length=this.size(); pos<length; pos++) {
                if(this.get(pos).compareTo(list.get(pos)) != 0) {
                    return false;
                }
            }
            //if up to this moment none of the elements returned false, lists are equal
            return true;
        }
    }

    /**
     * Compute hash code for the current list
     * @return integer value of hash code for the list
     */
    @Override
    public int hashCode() {
        int result = head.hashCode();
        result = HASHSALT * result + (current != null ? current.hashCode() : 0);
        return result;
    }

    /**
     * Convert MyLinkedList to an array of Objects
     * @return array of Objects
     */
    @Override
    public Object[] toArray() {
        //result array of length identical to size of MyLinkedList
        Object[] converted = new Object[this.size()];

        //assign values one by one
        for(int pos=0,length=this.size(); pos<length; pos++) {
            converted[pos] = this.get(pos);
        }
        return converted;
    }

    /**
     * Add an array of elements to MyLinkedList
     * @param c array of elements
     */
    @Override
    public void addAll(E[] c) {
        for(E element : c) {
            this.add(element);
        }
    }

    /**
     * Add an array of elements to MyLinkedList starting at specified index
     * @param index     position where to insert first element
     * @param c         array of elements
     */
    @Override
    public void addAll(int index, E[] c) {
        //check the correctness of index
        if(index < 0 || index > this.size()) {
            throw new MyIndexOutOfBoundsException();
        }

        int insertIndex = index;
        for(E element : c) {
            this.add(insertIndex, element);
            insertIndex++;
        }
    }

    /**
     * Clears the Linked List
     */
    @Override
    public void clear() {
        head.setNext(null);
    }

    /**
     * Checks whether current Linked List has no elements
     */
    @Override
    public boolean isEmpty() {
        return !head.hasNext();
    }

    /**
     * Returns an iterator for the Linked List
     */
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> current = head.getNext();
            @Override
            public boolean hasNext() {
                return current != null;
            }
            @Override
            public E next() {
                E result = current.getValue();
                current = current.getNext();
                return result;
            }
            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }

        /*
        Queue methods
        ================================================================
        */
    /**
     * Add new element to the end of the Queue
     * @param e	Element to add
     */
    @Override
    public void offer(E e) {
        this.add(e);
    }

    /**
     * Get the first element of the Queue or null if the Queue is empty
     * @return	element from the queue
     */
    @Override
    public E peek() {
        return this.getFirst();
    }

    /**
     * Get the first element of the Queue, and remove it
     * Return null, if Queue is empty
     * @return element from the queue
     */
    @Override
    public E poll() {
        return this.removeFirst();
    }

        /*
        End of Queue methods
        ================================================================
        */

        /*
        Stack methods
        ================================================================
        */

    /**
     * Push a new Element on top of the Stack
     * @param e		Element to push
     */
    @Override
    public void push(E e) {
        this.addFirst(e);
    }

    /**
     * Take element from the top of the Stack (and remove it)
     * @return Element, identical to the one on top of the Stack
     */
    @Override
    public E pop() {
        return this.removeFirst();
    }

	    /*
        End of Stack methods
        ================================================================
        */
}